package day1.linkedlist;

import org.w3c.dom.Node;

/**
 * @author pacai
 * @version 1.0
 */
public class ReverseList {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printList(head);
        head = reverseList(head);
        printList(head);
    }

    public static void printList(Node head) {
        while(head != null){
            System.out.print(head.data + " ");
            head = head.next;
        }
    }


    public static Node  reverseList(Node head) {
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        
        return pre;
    }

    static class Node<V>{
        public V data;
        public Node<V> next;

        public Node(V data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    public static class Queue<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public void offer(V data) {
            Node<V> cur = new Node<V>(data);
            if (isEmpty()) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                tail = cur;
            }
            size++;
        }

        public V poll() {
            V data = null;
            if (!isEmpty()) {
                data = head.data;
                head = head.next;
                size--;
            }
            if (head == null) {
                tail = null;
            }
            return data;
        }

        public V peek() {
            V data = null;
            if (!isEmpty()) {
                data = head.data;
            }
            return data;
        }


        public static class Stack<V> {
            private Node<V> head;
            private int size;

            public Stack() {
                head = null;
                size = 0;
            }

            public int size() {
                return size;
            }

            public boolean isEmpty() {
                return size == 0;
            }

            public void push(V data) {
                Node<V> node = new Node<>(data);
                if (head == null) {
                    head = node;
                } else {
                    node.next = head;
                    head = node;
                }
                size++;
            }

            public V pop() {
                V ans = null;
//                if(isEmpty()){
//                    return ans;
//                }
//                size--;
//                ans = head.data;
//                head = head.next;
//                return ans;
                if (!isEmpty()) {
                    ans = head.data;
                    head = head.next;
                    size--;
                }
                return ans;
            }

            public V peek() {
//                V ans = null;
//                if(!isEmpty()){
//                   ans = head.data;
//                }
//                return ans;

//            }
                return head == null ? null : head.data;
            }


        }
    }
}


